# 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
# 注意：答案中不可以包含重复的三元组。
# 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
# 满足要求的三元组集合为：
# [  [-1, 0, 1],
#   [-1, -1, 2]]


def threeSum(nums):
    len_sums = len(nums)
    if (len_sums == 0) or (len_sums == 1):
        return []
    hash_sum = {nums[0]+nums[1]: [[nums[0], nums[1]]]}
    count, res = 2, []
    while count <= len_sums - 1:
        if (-nums[count]) in hash_sum:
            for j in hash_sum[(-nums[count])]:
                mid = j[:]
                mid.append(nums[count])
                mid.sort()
                if mid not in res:
                    res.append(mid)
        for i in range(0, count):
            if (nums[i] + nums[count]) not in hash_sum:
                hash_sum[nums[i] + nums[count]] = [[nums[i], nums[count]]]
            else:
                hash_sum[nums[i] + nums[count]].append([nums[i], nums[count]])
        count += 1
    return res


def threeSum2(nums):
    nums.sort()
    len_sums, res = len(nums), []
    for i in range(0, len_sums - 2):
        if i != 0 and nums[i] == nums[i - 1]:
            continue
        j, h = i + 1, len_sums - 1
        while j < h:
            num_sum = nums[i] + nums[j] + nums[h]
            if num_sum == 0:
                res.append([nums[i], nums[j], nums[h]])
                j += 1
                h -= 1
                while j < h and nums[j] == nums[j - 1]:
                    j += 1
                while h > j and nums[h] == nums[h + 1]:
                    h -= 1
            elif num_sum < 0:
                j += 1
            else:
                h -= 1
    return res


print(threeSum2([0, 0, 0]))
